package com.markus.code.图.图1;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/19 16:41
 * todo: 最小生成树 P算法
 */
public class GraphP {
    public Set<Edge> graphP(Graph graph){
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new MyComparator());
        HashSet<Node> set = new HashSet<>();
        HashSet<Edge> edgeSet = new HashSet<>();
        for (Node node : graph.nodes.values()) {
            if (!set.contains(node)){
                set.add(node);
                for (Edge edge : node.edges) {
                    priorityQueue.add(edge);
                }
                while(!priorityQueue.isEmpty()){
                    Edge edge = priorityQueue.poll();
                    if (!set.contains(edge.to)){
                        edgeSet.add(edge);
                        Node toNode = edge.to;
                        set.add(toNode);
                        for (Edge edge1 : toNode.edges) {
                            priorityQueue.add(edge1);
                        }
                    }
                }
            }
            break;
        }
        return edgeSet;
    }
}
